import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: wangliuyang
 * @Date: 2021/4/20 15:16
 * @Description: 最长回文子串，manacher算法
 */
public class Solution_5 {
    public String longestPalindrome(String s) {
        //回文中心点
        int center = -1;
        //回文最右位置
        int right = -1;
        String str = manacherString(s);
        //回文半径
        int[] radius = new int[str.length()];
        //最大回文半径长度
        int max = Integer.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < str.length(); i++) {
            //获得能从已知条件得到的 i 扩出来的位置至少有多大
            radius[i] = i > right ? 1 : Math.min(radius[2*center - i],right - i + 1);
            while (i + radius[i] < str.length() && i - radius[i] > -1) {
                if (str.charAt(i + radius[i]) == str.charAt(i - radius[i])) {
                    radius[i]++;
                }else {
                    break;
                }
            }
            if (i + radius[i] > right) {
                center = i;
                right = i + radius[i] - 1;
            }
            if (radius[i] > max) {
                max = radius[i];
                index = i;
            }
        }
        //通过最大半径和最大半径所在点，进行拼接；无法区分出#
        StringBuilder stringBuilder = new StringBuilder();
        for (int j = index - max + 1; j <= index + max -1; j++) {
            if (str.charAt(j) != '#') {
                stringBuilder.append(str.charAt(j));
            }
        }
        return stringBuilder.toString();
    }
    public String manacherString(String str) {
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i)).append("#");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution_5().longestPalindrome("abaaba"));
    }
}
